

#include <algorithm>
#include <iostream>
#include <queue>
#include <vector>
#include <stack>

#include "common/utils.hpp"

bool isSameTree(TreeNode* p, TreeNode* q) {
    std::queue<TreeNode*> queue;
    queue.push(p);
    queue.push(q);

    while(!queue.empty()) {
        TreeNode* nodeP = queue.front();
        queue.pop();
        TreeNode* nodeQ = queue.front();
        queue.pop();

        if (nodeP == nullptr && nodeQ == nullptr) {

        } else if (nodeP != nullptr && nodeQ != nullptr) {
            if (nodeP->val != nodeQ->val) return false;

            queue.push(nodeP->left);
            queue.push(nodeQ->left);
            queue.push(nodeP->right);
            queue.push(nodeQ->right);
        } else {
            return false;
        }
    }

    return true;
}

extern TreeNode* commonRoot;

int main() {
    bool ret = isSameTree(commonRoot, commonRoot);
    std::cout << "is same: " << ret << "\n";
}